package main

import "fmt"

//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/binary-search
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

func search(nums []int, target int) int {
	if len(nums) == 1 {
		if nums[0] == target {
			return 0
		} else {
			return -1
		}
	}
	left := 0
	right := len(nums) - 1
	if target < nums[left] || target > nums[right] {
		return -1
	}
	for left != right {
		if right-left == 1 {
			if target > nums[left] && target < nums[right] {
				return -1
			}
			if target == nums[left] {
				return left
			}
			if target == nums[right] {
				return right
			}
		}

		if target > nums[(left+right)/2] {
			left = (left + right) / 2
		} else if target < nums[(left+right)/2] {
			right = (left + right) / 2
		} else {
			return (left + right) / 2
		}
	}
	return -1
}

func main() {
	ii := []int{-1, 5}
	i := search(ii, -1)
	fmt.Println(i)
}
